package 单词搜索;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param board string字符串一维数组
     * @param word string字符串
     * @return bool布尔型
     */
    static int N = 110, n, m;
    static boolean[][] st = new boolean[N][N];
    static char[][] g = new char[N][N];
    String s = new String();
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

    public boolean exist(String[] board, String word) {
        // write code here
        n = board.length;
        m = board[0].length();
        s = word;
        for (int i = 0; i < n; i++) {
            g[i] = board[i].toCharArray();
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == word.charAt(0)) {
                    for (int k = 0; k < n; k++) {
                        Arrays.fill(st[k], false);
                    }
                    if (dfs(new PII(i, j), 1)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean dfs(PII start, int u) {
        if (u == s.length()) {
            return true;
        }
        st[start.x][start.y] = true;
        for (int i = 0; i < 4; i++) {
            int x = start.x + dx[i], y = start.y + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m) {
                continue;
            }
            if (st[x][y]) {
                continue;
            }
            if (s.charAt(u) != g[x][y]) {
                continue;
            }
            if (dfs(new PII(x, y), u + 1)) {
                return true;
            }
            st[x][y] = false;
        }
        return false;
    }
}

class PII {
    int x, y;

    public PII(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
